package june6_13;

import java.util.Arrays;

/**
 * Problem:
 * =======
 * Find sum of contiguous  sub array which has largest sum, in the given one dimensional array.
 * - Kadane's Algorithm (Maximum sub array problem)
 *
 * Scan every value in the array
 *	- At every position, compute the maximum subarray at that position
 *	- Subarray will be either 0 or current element + the maximum sub array at previous position
 *
 *	- This is a vriant of a dynamic problem
 *
 *	Time Complexity is O(n)
 *
 * @author Udhaya
 *
 */
public class Kadane_MaximumSubArray 
{
	static int beginPoint = 0;
	static int endPoint = 0;
	
	static int kadaneMaximumSumOfSubArray(int[] array)
	{
		int currentMax 	= 0;
		int maxSoFar	= 0;
		int beginTemp 	= 0;
		
		for (int i = 0; i < array.length; i++)
		{
			currentMax += array[i];
			
			if (currentMax < 0)
			{
				currentMax = 0;
				beginTemp = i;
			}
			else if (currentMax > maxSoFar)
			{
				maxSoFar = currentMax;
				// beginTemp was noted while facing a negative value
				beginPoint 	= beginTemp + 1;
				endPoint	= i;
			}
		}
		
		return maxSoFar;
	}
	
	public static void main(String[] args)
	{
		int[] array = {-2, 1, -3, 4, 1, -1, 2, 1, -5, 4};
		int sumOfMaxSubArray = kadaneMaximumSumOfSubArray (array);
		System.out.println("Maximum Sub Array of " + Arrays.toString(array) + ": "
				+ "\nSum : " + sumOfMaxSubArray + 
				"\n Begins at : " + beginPoint + 
				"\n Ends at : " + endPoint);
		
	}
}
